#include <iostream>
#include <vector>


struct ListNode
{
    int val;
    ListNode*next;
};

void add_node(ListNode*&head,int data)
{
    ListNode*node = new ListNode;
    node->val = data;
    node->next = nullptr;

    if (!head)
        head = node;
    else 
    {
        ListNode*temp = head;
        while (temp->next)
        {
            temp = temp->next;
        }
        temp->next = node;
    }
}

void print_list(ListNode*head)
{
    ListNode*temp = head;
    while (temp)
    {
        std::cout<<temp->val<<"\n";
        temp = temp->next;
    }
}

ListNode* rearrage(ListNode*&head)
{
    // 首先判空，注意数据范围 0 <= k <= 100000
    if (!head||!head->next||!head->next->next)
    {
        return head;
    }

    // 使用两个std::vector<int>容器装链表
    std::vector<int>odds;
    std::vector<int>evens;

    // 链表奇偶项分别序列化
    ListNode*temp = head;
    int count = 1;
    while (temp)
    {
        // 奇偶数组处理部分，简单不难
        if (count&1)
        {
            odds.push_back(temp->val);
        }
        else 
        {
            evens.push_back(temp->val);
        }
        count++;
        temp = temp->next;
    }

    // 再次遍历将链表重赋值
    temp = head;
    for (auto it = odds.begin();it != odds.end();it++)
    {
        temp->val = *it;
        temp = temp->next;
    }
    for (auto it = evens.begin();it != evens.end();it++)
    {
        temp->val = *it;
        temp = temp->next;
    }

    return head;
}

int main()
{
    ListNode*head = nullptr;
    for (int i = 0;i < 10;i ++)
    {
        add_node(head,i);
    }

    print_list(head);
    // 调用重排函数
    head = rearrage(head);

    // 再次输出结果
    print_list(head);
    return 0;
}